#include <vector>
#include <tr1/unordered_map>
#include "bucket.cpp"
#include <iterator>
#include <algorithm>
#include <fstream>
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <string.h>

using namespace std;
using namespace tr1;

typedef unordered_map<int, Bucket::Bucket*> MAP_INT_BUCKET;
typedef Bucket::Bucket BUCKET;

class StreamSummary {

public :
	MAP_INT_BUCKET elements;
	vector<BUCKET> buckets;
	int k;

	StreamSummary(int k) {
		elements = MAP_INT_BUCKET();
		buckets = vector<Bucket::Bucket>();
		this->k = k;
	}

	string to_string() {
		stringstream out;
		for (vector<BUCKET>::iterator it = buckets.begin(); it != buckets.end(); it++) {
			out << (*it).to_string() << "\n";
		}
		return out.str();
	}

	int length() {
		return this->elements.size();
	}

	void add_element(int element) {
		if (this->elements.find(element) == elements.end()) {
			cerr << element <<  " not monitored" << endl;
			if (this->buckets.size() == 0 || this->buckets.at(0).value != 1) {
				cerr << "insert new bucket" <<endl;
				this->buckets.insert(buckets.begin(), *new Bucket());
			}
			this->elements.insert(pair<int, BUCKET*>(element, &this->buckets.at(0)));
			this->buckets.at(0).append(element);
		}
	}

	void increase_element(int element) {
		cerr << "increase" << endl;
		BUCKET * curr_bucket = this->elements.find(element)->second;
		cerr << "1. curr bucket" << (*curr_bucket).to_string() << endl;
		vector<BUCKET>::iterator it  = find(buckets.begin(), buckets.end(), (*curr_bucket));
		int bucket_idx = distance(this->buckets.begin(),it);
		cerr << "bucket idx: " <<  bucket_idx << endl;

		if (this->buckets.size() == bucket_idx + 1) {
			cerr << "buckets.size() == bucket_idx + 1" << endl;
			cerr << "3 curr bucket:" << (*curr_bucket).value << endl;
			this->buckets.push_back( *new Bucket((*curr_bucket).value +1) );
			curr_bucket = &buckets.at(bucket_idx);
			cerr << "#buckets:" << buckets.size() << endl;

			cerr << "3 curr bucket:" << (*curr_bucket).value << endl;
		} else if (this->buckets.at(bucket_idx+1).value > (*curr_bucket).value) {
			cerr << "this->buckets.at(bucket_idx+1).value > (*curr_bucket).value" << endl;
			this->buckets.insert(buckets.begin() + bucket_idx+1, *new Bucket((*curr_bucket).value+1));
		}
		cerr << "4 curr bucket "<< (*curr_bucket).to_string() << endl;
		(*curr_bucket).remove(element);
		cerr << "removed element" << endl;
		this->elements.insert(make_pair<int, BUCKET*>(element,&buckets.at(bucket_idx+1)));
		cerr << "assigned new el" <<endl;
		if (!(*curr_bucket).has_elements()) {
			delete curr_bucket;
			cerr <<  "deleted curr bucket" << endl;
		}
		cerr << (this->elements.find(element) == elements.end()) << endl;
		(*this->elements.find(element)->second).append(element);
		cerr << "append new el" << endl;
	}

	bool has_element(int element) {
		return this->elements.find(element) != this->elements.end();
	}

	int get_minimum() {
		if (this->buckets.size() > 0) {
			return buckets.at(0).first_element();
		} else {
			return -1;
		}
	}

	void replace_element(int old_el, int new_el) {
		this->elements[new_el] = this->elements[old_el];
		(*this->elements[new_el]).remove(old_el);
		(*this->elements[new_el]).append(new_el);
		this->elements.erase(old_el);
	}

	void insert(int el) {
		cerr << "inserting: " << el<< endl;
		if (has_element(el)) {
			cerr << "has el" << endl;
			increase_element(el);

		} else if (length() < this->k) {
			cerr << "< k" << endl;
			add_element(el);
		} else {
			cerr << "replace" << endl;
			int curr_min = get_minimum();
			if (curr_min > -1) {
				replace_element(curr_min, el);
				increase_element(el);
			} else {
				add_element(el);
			}
		}
		cerr << "finished insert"<< endl;
	}
};

void test_file() {
	StreamSummary ss(5);
	ifstream file;
	file.open("zipf.out", ifstream::in);
	if(!file) {
		cerr << "Summary: Could not open file: " << endl;
		exit(1);
	}

	int count = 0;
	while (file.good() && count < 5)
	{
		string key;
		getline(file,key);
		ss.insert(atoi ( key.c_str() ));
		count++;
		cerr << ss.to_string() << endl;
	}
	cerr << "finished" << endl;
	file.close();

	cerr << ss.length() << endl;
	cerr << ss.to_string() << endl;
}


int main() {
	cerr << "starting" << endl;
	test_file();
}
